#include <iostream>

using namespace std;

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode* next) : val(x), next(next) {}
};

ListNode* createList(int arr[], int n) {
    if (n == 0) {
        return nullptr;
    }

    ListNode* head = new ListNode(arr[0]);
    ListNode* cur = head;
    for (int i = 1; i < n; i++) {
        cur->next = new ListNode(arr[i]);
        cur = cur->next;
    }

    return head;
}

void printList(ListNode* head) {
    if (head == nullptr) {
        cout << "null" << endl;
    }

    while (head != nullptr) {
        cout << head->val;
        if (head->next != nullptr) {
            cout << "->";
        }
        head = head->next;
    }

    cout << endl;
}

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        if (head == nullptr) {
            return nullptr;
        }

        // 头节点可能被删除，所以创建一个哑节点指向头部节点
        ListNode* dummy = new ListNode(0, head);
        ListNode* cur = dummy;

        while (cur->next && cur->next->next) {
            // 如果cur->next和cur->next->next值相同
            // 删除cur->next以及后续值相等的所有节点
            if (cur->next->val == cur->next->next->val) {
                int x = cur->next->val;
                while (cur->next && cur->next->val == x) {
                    // 1 1 2
                    // 把cur想像成dummy，循环两次后，dummy指向了2
                    cur->next = cur->next->next;
                }
            } else {
                // 如果不想等，直接将cur指向cur->next
                cur = cur->next;
            }
        }

        return dummy->next;
    }
};

int main() {
    int arr[] = {1, 2, 3, 3, 4, 4, 5};
    int n = sizeof(arr) / sizeof(int);

    ListNode* head = createList(arr, n);
    printList(head);

    head = Solution().deleteDuplicates(head);
    printList(head);

    return 0;
}